Ông sinh năm 1650 tại vùng đất nay là thôn Phước Long, xã Chương Tín, huyện Phong Lộc (nay là xã Vạn Ninh, huyện Quảng Ninh, tỉnh Quảng Bình)[7], là con thứ ba của danh tướng Nguyễn Hữu Dật. Mẹ ông là bà Nguyễn Thị Thiện.

Nguyễn Hữu Cảnh là cháu 9 đời của Nguyễn Trãi. Ông nội của ông là Nguyễn Triều Văn (dòng Nguyễn Hữu, tước Triều Văn hầu, phò triều Lê và Nguyễn sơ), trước ở làng Gia Miêu, huyện Tống Sơn, tỉnh Thanh Hóa, sau theo chúa Tiên (Nguyễn Hoàng) di cư vào đất Thuận Hóa.[cần dẫn nguồn]

Cha ông, Chiêu Vũ hầu Nguyễn Hữu Dật, sinh nhiều con trai, trong đó có bốn người là tướng giỏi, kể theo thứ tự: Nguyễn Hữu Hào (tước Hào Lương hầu, tác giả truyện nôm Song tinh bất dạ), Nguyễn Hữu Trung (tước Trung Thắng hầu), Nguyễn Hữu Cảnh (tước Lễ Thành hầu) và Nguyễn Hữu Tín (tước Tín Đức hầu).

Dòng dõi con nhà tướng, lớn lên trong thời kỳ Trịnh – Nguyễn phân tranh, lại chuyên tâm luyện tập võ nghệ. Bởi vậy, tuy còn trẻ, nhưng ông đã lập được nhiều chiến công và đã được chúa Nguyễn Phúc Tần phong chức Cai cơ (một chức võ quan thuộc bậc cao) vào lúc tuổi độ 20, được người đương thời gọi tôn là "Hắc Hổ" (vì ông sinh năm Dần và vì có nước da ngăm đen, vóc dáng hùng dũng).